// https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 二分查找解决旋转排序数组搜索问题
// 2. 第一阶段：查找旋转点（最大值的索引）
// 3. 第二阶段：在有序的两段中分别进行二分查找
// 4. 使用左闭右开二分模板，避免边界错误
// 5. 时间复杂度：O(logn)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int binarySearch(vector<int>& nums, int left, int right, int target)
    {
        int l = left - 1, r = right + 1;
        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        if (l != -1 && nums[l] == target)
        {
            return l;
        }   

        return -1;
    }

    int search(vector<int>& nums, int target) 
    {
        int m = nums.size();

        int l = -1, r = m;
        int key = nums[0];

        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] >= key)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        if (l == m - 1)
        {
            return binarySearch(nums, 0, m - 1, target);
        }
        else 
        {
            int index1 = binarySearch(nums, 0, l, target);
            int index2 = binarySearch(nums, l + 1, m - 1, target);

            if (index1 != -1) return index1;
            if (index2 != -1) return index2;
            return -1;
        }
    }
};

int main()
{
    vector<int> nums1 = {4,5,6,7,0,1,2}, nums2 = {4,5,6,7,0,1,2};
    int target1 = 0, target2 = 3;

    Solution sol;

    cout << sol.search(nums1, target1) << endl;
    cout << sol.search(nums2, target2) << endl;

    return 0;
}